package sort

import "math/rand"

// 快速排序；快排

func QuickSort(a []int) {
	if len(a) <= 1 {
		return
	}
	// pivot点的选择很重要
	pivot := a[0]
	l, r := 0, len(a)-1
	for i := 1; i <= r; {
		if a[i] > pivot {
			a[i], a[r] = a[r], a[i]
			r--
			// 不能移动i
		} else {
			a[i], a[l] = a[l], a[i]
			l++
			i++
		}
	}
	QuickSort(a[:l])
	QuickSort(a[l+1:])
}

func Partition(data []int, start, end int) int {
	if len(data) == 0 {
		return -1
	}
	var index = RandomInRange(start, end)
	data[index], data[end] = data[end], data[index]

	var small = start - 1
	for index = start; index < end; index++ {
		if data[index] < data[end] {
			small++
			if small != index {
				data[index], data[small] = data[small], data[index]
			}
		}
	}

	small++
	data[small], data[end] = data[end], data[small]

	return small
}

func RandomInRange(start, end int) int {
	return rand.Intn(end-start+1) + start
}
